# JZ1 二维数组中的查找
# 描述
# 在一个二维数组array中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。
# 请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
# [
# [1,2,8,9],
# [2,4,9,12],
# [4,7,10,13],
# [6,8,11,15]
# ]
# 给定 target = 7，返回 true。
# 给定 target = 3，返回 false。
# 0 <= array.length <= 500
# 0 <= array[0].length <= 500
# 你能给出时间复杂度为 O(n+m) 的解法吗？（n,m为矩阵的长和宽）
#
# 示例
# 输入：
# 7,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]
# 返回值：
# true
# 说明：
# 存在7，返回true
#
# 输入：
# 3,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]
# 返回值：
# false
# 说明：
# 不存在3，返回false

# 核心代码模式
# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # 防止空数组
        if len(array) == 1 and len(array[0]) == 0:
            return 0
        # 方法1：遍历
        #         for i in range(0,len(array)):
        #             for j in range(0,len(array[0])):
        #                 print(array[i][j])
        #                 if target == array[i][j]:
        #                     return 1
        #                 elif target < array[i][j]:
        #                     break
        #         return 0

        # 方法2：二分法 右上角初始化
        x1 = len(array[0]) - 1  # 第几列
        x2 = 0  # 第几行
        while x1 >= 0 and x2 < len(array):
            val = array[x2][x1]
            print(val, x1, x2)
            if target == val:
                print("#")
                return 1
            elif target > val:
                x2 = x2 + 1
            else:
                x1 = x1 - 1
        return 0
